package 树;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 具有所有节点的最小子树.java
 * @Description TODO
 * @createTime 2020年10月10日 21:53:00
 * 给定一个根为 root 的二叉树，每个结点的深度是它到根的最短距离。
 *
 * 如果一个结点在整个树的任意结点之间具有最大的深度，则该结点是最深的。
 *
 * 一个结点的子树是该结点加上它的所有后代的集合。
 *
 * 返回能满足“以该结点为根的子树中包含所有最深的结点”这一条件的具有最大深度的结点。
 *
 *  
 *
 * 示例：
 *
 * 输入：[3,5,1,6,2,0,8,null,null,7,4]
 * 输出：[2,7,4]
 * 解释：
 *
 * 我们返回值为 2 的结点，在图中用黄色标记。
 * 在图中用蓝色标记的是树的最深的结点。
 * 输入 "[3, 5, 1, 6, 2, 0, 8, null, null, 7, 4]" 是对给定的树的序列化表述。
 * 输出 "[2, 7, 4]" 是对根结点的值为 2 的子树的序列化表述。
 * 输入和输出都具有 TreeNode 类型。
 *
 */
public class 具有所有节点的最小子树 {
//    class Solution {
//        Map<TreeNode, Integer> map = new HashMap<>();
//
//        public TreeNode subtreeWithAllDeepest(TreeNode root) {
//            if (root == null) {
//                return null;
//            }
//            int ld = getDepth(root.left);
//            int rd = getDepth(root.right);
//            if (ld == rd) {
//                return root;
//            } else if (ld > rd) {
//                return subtreeWithAllDeepest(root.left);
//            } else {
//                return subtreeWithAllDeepest(root.right);
//            }
//        }
//
//        public int getDepth(TreeNode node) {
//            if (node == null) {
//                return 0;
//            }
//            if (map.containsKey(node)) {
//                return map.get(node);
//            }
//            int ld = getDepth(node.left);
//            int rd = getDepth(node.right);
//            map.put(node, Math.max(ld, rd) + 1);
//            return map.get(node);
//        }
//    }
//

}
